package 七大排序;

import java.util.Arrays;

/*
 *归并排序的思想
 *      1。先将数组分割，直到分到数组中只有一个元素
 *      2.在分的过程中，步进行任何比较
 *      3.分到无法在分的时候，在排序合并
 */
public class 归并排序 {
    static int count = 0;
    public static void main(String[] args) {
        int[] arr = {2,4};
        int[] temp = new int[arr.length];
        int left = 0;
        int right = arr.length-1;
        mergeSort(arr,left,right,temp);
        System.out.println(Arrays.toString(arr));
        System.out.println(count);
    }
    /*
    第一步：
        1，分解数组，将数组分解到最小，及每一个小数组只含一个元素
        2.向左分解
        3.向右分解、
     */

    /**
     *
     * @param arr 需要排序的数组
     * @param left 数组的最左边的下标
     * @param right 数组的最右边的下标
     * @param temp 临时数组
     */
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        int mid = (left+right)/2;//设置数组中间下标
        //如果left==right，说明已经分解到只有一个元素，此时退出，惊醒排序
        if (left < right){
            //向左递归分解
            mergeSort(arr,left,mid,temp);
            //向右递归分解
            mergeSort(arr,mid+1,right,temp);
        }
        //归并
        merge(arr,left,mid,right,temp);
    }
    //    第二步进行归并

    /**
     *
     * @param arr 需要归并的数组
     * @param left  需要归并数组的最左边的下标
     * @param mid   将数组二分以后的中间下标
     * @param right 需要归并数组的最右边的下标
     * @param temp  用来存放排序的临时数组下标
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//将数组归并时要比较两个小数组元素之间大小，将左边的数组第一个元素的下标色湖之为i
        int j = mid +1;//将数组归并时要比较两个小数组元素之间大小，将右边的数组第一个元素的下标色湖之为j
        int t = 0;//将数组归并时要使用到临时数组用来存放元素，t表示临时数组的下标
        //比较两边的数组元素的大小
        int k = 0;
        while(i <= mid && j <= right){
            if (arr[i] < arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
                k++;
            }else {
                temp[t] = arr[j];
                t++;
                j++;
                count++;
            }
        }
        if (j > right){
            count = count + (mid - i + k) * (right - mid - k);
        }
        //当比较右一方数组的元素到达最后一个，而另一方数组还有元素时，将剩余的元素复制到临时数组中
        while (i <= mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j <= right){
            temp[t] = arr[j];
            t++;
            j++;
        }
        //最后把temp中的数据复制到arr中
        t = 0;
        int tempLeft = left;
        while(tempLeft <= right){
            arr[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }
    }
}
